package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/12/20 17:29
 */
public class LC475供暖器 {

    public static void main(String[] args) {
//        int[] houses = {1, 2, 3, 4}, heaters = {1, 4};
        int[] houses = {1, 5}, heaters = {10};
//        int[] houses = {1, 5, 8, 10}, heaters = {5};
        System.out.println(findRadius(houses, heaters));
    }

    public static int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int left = 0, right = Math.max(houses[houses.length - 1], heaters[heaters.length - 1]);
        while (left < right) {
            int mid = (left + right) >>> 1;
            boolean cover = true;
            for (int i = 0, j = 0; i < houses.length; i++) {
                while (j < heaters.length && heaters[j] + mid < houses[i]) j++;
                if (j == heaters.length && i <= houses.length - 1) {
                    cover = false;
                    break;
                }
                if (houses[i] < heaters[j] - mid || houses[i] > heaters[j] + mid) {
                    cover = false;
                    break;
                }
            }
            if (cover) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}
